//
// Created by gushen610140 on 2024/4/18.
//

#ifndef DATASTRUCTURECOURSE_GPARENTINGTREE_H
#define DATASTRUCTURECOURSE_GPARENTINGTREE_H

#include <iostream>

template<typename T>
class _GParentingNode {
public:
    _GParentingNode<T> *parent;
    T data;
    _GParentingNode<T> *left;
    _GParentingNode<T> *right;

    explicit _GParentingNode(T data) : parent(nullptr), data(data), left(nullptr), right(nullptr) {}
};

template<typename T>
class [[maybe_unused]] GParentingTree {
private:
    _GParentingNode<T> *_root;

    _GParentingNode<T> *_createPreorder(_GParentingNode<T> *parent) { // NOLINT(*-no-recursion)
        T value;
        std::cin >> value;
        if (value == 0)
            return nullptr;
        auto node = new _GParentingNode<T>(value);
        node->parent = parent;
        node->left = _createPreorder(node);
        node->right = _createPreorder(node);
        return node;
    }

    _GParentingNode<T> *_getNode(_GParentingNode<T> *node, T value) {
        if (node == nullptr) {
            return nullptr;
        }
        if (node->data == value) {
            return node;
        }
        auto left = _getNode(node->left, value);
        auto right = _getNode(node->right, value);
        return left != nullptr ? left : right;
    }

    void _printParents(_GParentingNode<T> *node) {
        if (node == nullptr || node->data == 0) {
            return;
        }
        std::cout << node->data << " ";
        _printParents(node->parent);
    }

public:

    GParentingTree() : _root(nullptr) {}

    [[maybe_unused]] void createPreorder() {
        auto dummy = new _GParentingNode<T>(0);
        _root = _createPreorder(dummy);
    }

    [[maybe_unused]] _GParentingNode<T> *getNode(T value) {
        return _getNode(_root, value);
    }

    [[maybe_unused]] void printParents(_GParentingNode<T> *node) {
        _printParents(node);
        std::cout << std::endl;
    }

};


#endif //DATASTRUCTURECOURSE_GPARENTINGTREE_H
